INSTITUTO SUPERIOR DE ECONOMIA E GESTÃO

MAEG – Investigação Operacional II – PERT-CPM

______________________________________________________________________

Exemplo Protótipo (adaptado de Hillier and Lieberman, in Introduction to Operations Research, seventh edition, pag. 469). A RELIABLE CONSTRUCTION COMPANY acaba de ganhar por $5,4 milhões um concurso para a construção de uma fábrica para uma grande empresa industrial. O dono da obra precisa da fábrica pronta no prazo de um ano. Do contracto, entre outras, fazem parte as seguintes cláusulas:

Uma penalidade de $300 000 se a RELIABLE não entregar a obra pronta no prazo de 47 semanas a partir da assinatura do contracto;

Um incentivo a uma entrega mais rápida, estando previsto um bónus de $150 000 se a obra for entre no prazo de 40 semanas.

Como director responsável pela obra foi nomeado o engenheiro David Perty, cuja principal missão será entregar a obra no prazo de 47 semanas, ou menos, com o orçamento de custos que consta da proposta. Como ele, por enquanto, tem dúvidas da possibilidade de realizar a obra em 40 semanas sem incorrer em custos excessivos, vai focalizar-se no seu plano inicial de 47 semanas.

O director vai inicialmente concentrar-se na constituição da equipa (supervisores) para com ele gerir as diferentes actividades da construção da fábrica. O quadro abaixo indica a lista das várias actividades, relação entre elas, e respectivas durações.

Lista das Actividades

Actividade	Descrição	Antecessora Imediata	Duração estimada
A	Terraplanagens	-	2 Semanas
B	Fundações	A	4 Semanas
C	Paredes	B	10 Semanas
D	Telhado	C	6 Semanas
E	Canalização exterior	C	4 Semanas
F	Canalização interior	E	5 Semanas
G	Tapume exterior	D	7 Semanas
H	Pintura exterior	E, G	9 Semanas
I	Electrificação	C	7 Semanas
J	Revestimento das paredes	F, I	8 Semanas
K	Revestimento do chão	J	4 Semanas
L	Pintura interior	J	5 Semanas
M	Suportes e Iluminação exteriores	H	2 Semanas
N	Suportes e Iluminação interiores	K, L	6 Semanas

Para programar as actividades o Sr. Perty reúne com os respectivos supervisores, pretendendo conhecer as durações estimadas para as diversas actividades. Essas estimativas encontram-se na última coluna do quadro anterior.

Tendo em conta a informação disponibilizada, o Sr. Perty pretende ter respostas para as seguintes questões:

Como pode o projecto ser representado graficamente para visualizar a sequência e relação entre as actividades?;

Qual o tempo necessário para realizar o projecto assumindo que não se verifica qualquer atraso?;

Quando é que individualmente as actividades podem (o mais cedo) ser iniciadas e (o mais tarde) terminadas?;

Quais as actividades que não podem sofrer atrasos sob pena de comprometerem a data de finalização do projecto?;

Para as outras actividades, para cada uma delas qual o atraso máximo que pode ser tolerado sem comprometer (atrasar) o projecto?;

Qual o atraso máximo que cada uma actividade pode ter sem comprometer a data mais cedo dos acontecimentos seguintes?;

Para visualizar a evolução do projecto, o Sr. Perty pretende estabelecer um calendário (Time Schedule) do projecto;

Sabendo que há incerteza na realização das actividades e os supervisores apresentaram estimativas optimistas, mais prováveis e pessimistas, dadas pelo quadro abaixo, qual a probabilidade de o projecto ser cumprido na data estabelecida em contrato? Comente;

Durações Estimadas das Actividades (em semanas)

Actividade	Duração Optimista	Duração Mais Provável	Duração Pessimista
A	1	2	3
B	2	3,5	8
C	6	9	18
D	4	5,5	10
E	1	4,5	5
F	4	4	10
G	5	6,5	11
H	5	8	17
I	3	7,5	9
J	3	9	9
K	4	4	4
L	1	5,5	7
M	1	2	3
N	5	5,5	9

Admitindo que se dispõe de um orçamento de custos adicionais, qual o montante mínimo a gastar de modo a completar o projecto em 40 dias, considerando a informação do quadro abaixo?;

Admitindo que o dono da obra em vez do bónus associado à realização do projecto em 40 semanas propõe uma solução mais flexível, que consiste em estabelecer um bónus de $25 000 por cada semana de antecipação em relação à data de 47 semanas, para que prazo deve ser programada a obra, considerando a informação do quadro abaixo?

Custos de Aceleração nas Actividades
Duração (semanas)	Custo ($ mil)
Actividades	Normal	Acelerada	Normal	Acelerado
A	2	1	180	280
B	4	2	320	420
C	10	7	620	860
D	6	4	260	340
E	4	3	410	570
F	5	3	180	260
G	7	4	900	1020
H	9	6	200	380
I	7	5	210	270
J	8	6	430	490
K	4	3	160	200
L	5	3	250	350
M	2	1	100	200
N	6	3	330	510

2.	(Exemplo 6.5-1, TAHA, pag.278) Um editor tem um contrato com um autor para publicar um livro. As actividades (simplificadas) associadas à produção do livro encontram-se descritas abaixo. O autor deverá submeter à apreciação do editor uma cópia e um ficheiro de computador do respectivo manuscrito.

Represente a rede do projecto e determine a respectiva duração, identificando o caminho crítico.

Actividade	Duração (Semanas)	Predecessora
A Leitura do Manuscrito	3	-
B Preparação do tipo de Páginas	2	-
C Design da Capa	4	-
D Preparação do Trabalho Artístico	3	-
E Aprovação do Manuscrito e tipo Páginas	2	A, B
F Formatação do Livro	4	E
G Revisão pelo Autor da Formatação	2	F
H Revisão pelo Autor do Trabalho Artístico	1	D
I Produção das Chapas de Impressão	2	G, H
J Produção e Encadernação do Livro	4	C, I

Considere um projecto de construção de um parque industrial cujas actividades são as seguintes:

Actividade: A B C D E F G H I J L M

Ant.Imed. - - - A,B,C B,C B,C C D,E,F,G D,E,F,G FG I,J H,I,J

Estabeleça a rede, com actividades nos arcos, deste projecto com um mínimo de actividades fictícias.

4.	Considere-se um projecto de construção de um edifício que envolve as seguintes actividades:

Actividade	Duração (Dias)	Predecessora
A Escavações	2	-
B Fundações	4	A
C Paredes	10	B
D Canalizações Exteriores	4	C
E Telhado	6	C
F Reboco	7	E
G Pintura Exterior	9	D, F
H Canalizações Interiores	5	D
I Electrificação	7	C
J Revestimento Interior	8	H, I
K Equipamentos Exteriores	2	G
L Colocação do Soalho	4	J
M Pintura interior	5	J
N Equipamentos Interiores	6	L, M

Representar numa rede de projecto as actividades e as suas relações de precedência. Determine a respectiva duração, identificando o caminho crítico.

5.	Considere um projecto constituído pelas actividades A, B, …, H cujas durações e relações de precedência são as indicadas na tabela. Admita ainda que não possível iniciar a actividade G antes de decorrerem 3 dias sobre o início da actividade F e que a actividade E não pode ter início antes de decorridos 2 dias sobre o fim das suas predecessoras.

Determine a duração mínima do projecto, as actividades críticas e as margens para todas as actividades.

Actividade	Duração (Dias)	Predecessora
A	10	-
B	15	A
C	12	B
D	13	B
E	4	C, D
F	8	C
G	7	C
H	17	G

6.	A rede que se apresenta de seguida diz respeito a um projecto, para o qual se pode considerar que os tempos de execução das tarefas são variáveis aleatórias normais e independentes, cujos valores esperados e variâncias são os indicados sob cada arco da rede (valor esperado; variância).

1 2 5 4 6 7 8 A(10; 4) D(5; 1) B(14; 10) C(8; 5) 3 G(10; 5) E(10; 6) F(10; 5) H(5; 1) f f f f

Indique, justificando, as actividades sobre as quais é sensato tomar mais atenção;

Determine a probabilidade do tempo de execução do caminho {(1,2); (2,4); (4,5); (5,8)} ser superior ao tempo de execução do caminho {(1,2); (2,4); (4,5); (5,6); (6,8)}.

7.	Considere um projecto constituído pelas actividades A,...,H, com as seguintes características:

Actividade	(i,j)	(aij,mij,bij)
A	(1,2)	(3,5,7)
B	(1,3)	(4,6,8)
C	(2,3)	(1,3,5)
D	(2,4)	(5,8,11)
E	(3,5)	(1,2,3)
F	(3,6)	(9,11,13)
G	(4,6)	(1,1,1)
H	(5,6)	(10,12,14)

e em que a actividade D precede as actividades G e H.

a)	Calcule a duração esperada do projecto;

b)	Para cada acontecimento j, determine a probabilidade de j ocorrer até à data Sj a seguir indicada, isto é, calcule P[ej ≤ Sj], com

j	2	3	4	5	6
Sj	5	11	12	14	26

8.	Considere um pequeno projecto cujas actividades principais, durações e relações de precedência, são as seguintes:

Durações
Actividades	Precedentes	Optimista	Mais provável	Pessimista
A	-	25	28	43
B	-	38	52	54
C	-	35	40	45
D	A	24	29	40
E	B, G	17	19	27
F	C	35	40	75
G	A	35	40	45

Determine a duração esperada do projecto e a sua variância;

Qual a probabilidade da duração do projecto ser não superior a 95 dias?;

Qual o prazo de realização que se poderá cumprir com probabilidade de 99%?;

Qual a probabilidade de C e F durarem, em conjunto, mais do que o caminho crítico?

9.	Considere um projecto, cujas actividades, durações (em dias), relações de precedência, acelerações máximas e custos unitários de aceleração são as seguintes:

Actividade	Act. Precedente	Duração normal	Aceleração máxima	C.U. Aceleração
A	-	35	10	5
B	-	42	12	4
C	A	21	7	6,5
D	A	56	15	6
E	B, C	14	4	8
F	B, C	77	20	4,5
G	D	7	3	7,5
H	D, E	84	20	5

Determine o caminho crítico, considerando as durações normais indicadas;

Formule o problema com problema de Programação Linear e resolva-o através de um dos “softwares” conhecidos;

Acha que é possível executar o projecto em menos 25 dias de duração do que a que decorre das durações normais? Se sim, quais os custos adicionais para conseguir esta redução?;

Suponha que por cada dia de antecipação se tem um prémio de 10 u.m.. Determine a duração óptima.

10.	Considere um projecto de construção de um edifício cujas principais tarefas são as que se encontram na tabela seguinte. Com base nas relações de precedência aí exibidas:

Tarefas	Tarefas sucessoras	Duração (semanas)	Nº de trabalhadores
A	Fundações	B	5	5
B	Estrutura	C, I	8	6
C	Paredes	D, G, H, L	14	3
D	Tecto	E	10	3
E	Telhado	-	3	4
F	Pinturas	J	31	2
G	Instalação eléctrica	F, J	11	2
H	Condutas	F, M	10	3
I	Soalhos	J	9	3
J	Acabamentos interiores	-	3	4
L	Acabamentos exteriores	-	10	4
M	Sanitários	J	5	1

Determine a duração do projecto;

Indique as actividades críticas e o caminho crítico;

Calcule as margens livres e totais para cada uma das actividades não críticas;

Tendo em conta o número de trabalhadores necessários para realizar cada uma das tarefas e admitindo que os trabalhadores estão aptos para executar qualquer tarefa, apresente uma calendarização que lhe permita ter, em cada momento, não mais do que seis trabalhadores no edifício.